The invention relates to techniques for reading two dimensional code such as MaxiCode. Aspects of the invention are particularly useful in imaging optical code readers which are designed to read various kinds of optical code.
Optical codes are patterns made up of image areas having different light reflective or light emissive properties, which are typically assembled in accordance with a priori rules. The term xe2x80x9cbar codexe2x80x9d is sometimes used to describe certain kinds of optical codes. The optical properties and patterns of optical codes are selected to distinguish them in appearance from the background environments in which they are used. Devices for identifying or extracting data from optical codes are sometimes referred to as xe2x80x9coptical code readersxe2x80x9d of which bar code scanners are one type. Optical code readers are used in both fixed or portable installations in many diverse environments such as in stores for check-out services, in manufacturing locations for work flow and inventory control and in transport vehicles for tracking package handling. The optical code can be used as a rapid, generalized means of data entry, for example, by reading a target bar code from a printed listing of many bar codes. In some uses, the optical code reader is connected to a portable data processing device or a data collection and transmission device. Frequently, the optical code reader includes a handheld sensor which is manually directed at a target code.
Most conventional optical scanning systems are designed to read one-dimensional bar code symbols. The bar code is a pattern of variable-width rectangular bars separated by fixed or variable width spaces. The bars and spaces have different light reflecting characteristics. One example of a one dimensional bar code is the UPC/EAN code used to identify, for example, product inventory. An example of a two dimensional or stacked bar code is the PDF417 bar code. A description of PDF417 bar code and techniques for decoding it are disclosed in U.S. Pat. No. 5,635,697 to Shellhammer et al. and assigned to Symbol Technologies, Inc., which patent is incorporated herein by reference.
Conventional codes are known which are based on a two dimensional grid whose geometry is independent of data content. The grid may be a plane tiled by regular polygons such as squares or hexagons. Typically a black or white feature or polygon is located at each grid location.
One such two dimensional optical code known in the art is MaxiCode. A portion of a conventional MaxiCode symbol is shown in FIG. 4. MaxiCode is a matrix symbology made up of offset rows of hexagonal modules arranged around a finder pattern. A MaxiCode symbol may consist of a unique central finder pattern: up to 3 dark concentric rings and 3 included light areas, sometimes called a xe2x80x9cbulls-eyexe2x80x9d. The central finder pattern is surrounded by an approximately square-shaped array of 33 offset rows of hexagonal modules. The 33 rows in the symbol alternate between 30 and 29 modules in width. Orientation information (rotation) is provided by 6 patterns of three modules each located adjacent to the bulls-eye. Data is carried in the presence or absence of darkened modules within the hexagonal grid. A binary encoding scheme may be used to represent information in black (low reflectivity) and white (high reflectivity). MaxiCode is described in detail in the publication xe2x80x9cInternational Symbology Specificationxe2x80x94MaxiCodexe2x80x9d, by AIM International, Inc. (hereinafter xe2x80x9cAIM Specificationxe2x80x9d).
Various optical codes including MaxiCode can be read employing imaging devices. For example an image sensor may be employed which has a two dimensional array of cells or photo sensors which correspond to image elements or pixels in a field of view of the device. Such an image sensor may be a two dimensional or area charge coupled device (CCD) and associated circuits for producing electronic signals corresponding to a two dimensional array of pixel information for a field of view. An imaging engine usable in reading MaxiCode is disclosed in U.S. patent application Ser. No. 09/096,578 filed Jun. 12, 1998, entitled IMAGING ENGINE AND METHOD FOR CODE READERS to Correa et al. which is hereby incorporated by reference. Electronic circuits in or associated with the imaging engine may be provided to decode MaxiCode.
The above-mentioned AIM Specification discloses a frequencyxe2x80x94domain technique to decode MaxiCode. In such processes three principal MaxiCode axes, assumed to correspond to the hexagon grid, are found in two dimensional pixel data using a Fourier transform technique. Grid locations for the modules are then determined by use of inverse Fourier transform techniques. However, such techniques require computationally intensive, two dimensional transforms, which have long processing times particularly at high resolution levels preferred for accurate decoding. Moreover, such techniques may not accurately accommodate tilted or warped MaxiCode symbols.
Accordingly, it is an object of the present invention to provide a fast and efficient technique for decoding grid-based two dimensional code such as MaxiCode.
It is another object of the present invention to provide a technique for decoding grid based, two dimensional code which better tolerates tilt and/or warping of the code symbol as seen by the image sensor.
It is another object of the present invention to provide a technique for decoding MaxiCode which produces an accurate grid mapping which can better accommodate symbol grid distortion and which can take into account tilt in the plane of the MaxiCode symbol with respect to the optical axis of the image sensor.
In U.S. Pat. No. 5,637,849 to Wang et al., it has been proposed to extract data from a MaxiCode symbol using a spatial domain technique, without frequency domain transforms. The technique includes identifying two intersecting diameters of at least one traversal line having an alignment normal to the sides of the hexagonal data cells. In the case that the symbol is on a non-planar surface, Wang et al. teaches that the top row of data cells must be sampled by an angled row of pixels and, the middle row of data samples by a horizontal row of pixels and intermediate rows of data cells sampled at angles interpolated between the top angle and horizontal. Alternatively, or in addition, a normalization routine may be implemented for individual rows of data cells.
MaxiCode is a type of matrix code which lacks extensive self-synchronization such as that built into PDF417. Some variants of Data Matrix also fall into this category. To decode such types of two dimensional bar codes, a projection or interpolation based on a single line or even a few lines is not adequate and could result in module displacement.
Accordingly, it is an object of the present invention to provide more accurate techniques for mapping a code grid, particularly one which lacks extensive self-synchronization such as MaxiCode.
It is another object of the present invention to provide techniques for more accurately and efficiently decoding grid-based two dimensional codes in situations where the code symbol does not lie in a plane normal to the optical axis of the image sensor.
It is another object of the present invention to provide techniques for decoding grid-based two dimensional codes in situations where the code symbol or the image of the code symbol is progressively distorted from the nominal grid pattern on which the code is based.
These and other objects and features of the invention will be apparent from this written description and drawings.
The disclosure relates to techniques for determining the presence, orientation and location of features in an image of a two dimensional optical code especially grid-based codes whose geometry is independent of data content, and more especially grid-based code based on repeating non-rectangular module shapes such as hexagons. The techniques are adapted for use in locating finder patterns and orientation modules, and in mapping data in an image pixel plane with grid locations in a grid-based two dimensional code to account for size, rotation, tilt, warping and distortion of the code symbol. Where such a code is a MaxiCode, techniques are disclosed for determining the presence and location of the MaxiCode bulls-eye and orientation modules.
More particularly, a preferred embodiment of the present invention is a method for determining the presence and location of a MaxiCode symbol bulls-eye and the orientation of the symbol in pixel data obtained by an optical code reader. In this method a candidate center in a run of pixels having a color indicative of the center area of the bulls-eye is identified. The candidate center is tested to determine if adjacent pixel runs have a predetermined amount of mirror symmetry with respect to the candidate center. Plural points are located on axes radiating from the identified run and intersecting an edge of a ring of the MaxiCode bulls-eye. An ellipse is fitted to the located points and the ellipse is expanded outwardly to estimate the location of orientation modules of the MaxiCode. The orientation of the MaxiCode symbol is determined from information read from the orientation modules.
The fitted ellipse may be required to have major and minor dimensions having a ratio of 2:1 or less. If this ratio is not met, the image may be rejected as exhibiting too great a tilt. A least squares fit may be employed to find the major and minor dimensions of the ellipse fitted to the located points. In preferred embodiments the ring edge located and fitted is the inner edge of the outermost black ring of the MaxiCode bulls-eye. Up to 24 points may be used in the least square fit to find the major and minor dimensions of the ellipse.
Another preferred embodiment of the present invention includes techniques for associating pixel data in a pixel plane of a two dimensional grid-based symbol with corresponding modules in the grid. In accordance with this technique, subsets of the pixel data having a known association with plural seed modules such as MaxiCode orientation modules, are identified. The coefficients of an Euler transform are determined through a least-squared best-fit method using the identified association between the pixel data subsets and the seed modules. Using the Euler transform, other locations in the pixel plane are associated with additional symbol modules.
In preferred embodiments of this technique, more than six seed modules are employed. In the case that the symbol is a MaxiCode symbol, the seed modules may be a selected subset of the 18 orientation hexagon modules of the MaxiCode symbol, preferably as many of such modules whose locations are readily distinguishable. The technique is usable, for example, where the grid-based symbol is not located in any single plane perpendicular to the optical axis of the optical code reader, such as where the symbol lies on a tilted plane or is printed on the curved face of a can.
In another preferred embodiment of the present invention a method is employed for decoding a MaxiCode symbol to obtain data from the primary data modules and secondary data modules located on the hexagonal grid. In such a method the central finder pattern is located and then the orientation modules located based on the location of the central finder pattern. The location of primary data modules of the MaxiCode are found based on the previously determined locations of the orientation modules. The secondary data modules are sequentially locating outwardly from the primary message modules toward the edge of the symbol using previously located positions of adjacent modules. Secondary data modules are located in a successive radial progression of rings of hexagons outward toward the edges of the symbol.
In preferred embodiments the location of secondary data modules are estimated using the positions of adjacent modules and just past adjacent modules. The location of a first set of secondary data modules may be refined by centering black/white transitions before locating a next set of secondary data modules further outward for the central finder pattern. Deviations from a regular hexagonal grid are accumulated as the location of secondary data modules proceeds outwardly from the central finder pattern.
The initial location of the central finder pattern may be based on finding a candidate bulls-eye center by testing local symmetry about selected axes. A candidate sequence of alternating runs running in a horizontal direction (with respect to the image detector) may be tested, the 5th run being the candidate center run.
Initially, the candidate sequence is evaluated to verify that the lengths of the runs are within a predetermined proportion of a selected one of the runs.
In preferred embodiments, a candidate center may be further tested by evaluating pixel data vertically above and below the candidate center for approximate mirror symmetry in the location of corresponding black/white transitions in the data. In one embodiment, horizontal and vertical distances may be subjected to a ratio test to evaluate the image. Yet further testing of a candidate center may be done by evaluating pixel data on diagonal lines passing through the candidate center for appropriate mirror symmetry in the location of corresponding black/white transitions in the data. If all tests are passed, the candidate center and/or black/white transition data may be used to locate additional features of the MaxiCode.
The scope of the present invention is defined in the claims.